package com.lwx.leetcode.offer.middile;

/**
 * 字符串是否存在矩阵中
 */
public class Offer12 {
    public static void main(String[] args) {
        Offer12 o = new Offer12();
        char[][] board = {{'A','A'}};
        String word = "AAA";
        System.out.println(o.exist(board, word));
    }

    private boolean[][] visited;
    private int[][] direction = {{-1,0},{0,1},{1,0},{0,-1}};
    private int m,n;


    public boolean exist(char[][] board, String word) {

        if(board == null || board[0] == null || word == null || word.length() == 0){
            return false;
        }

        //行数
        m = board.length;
        //列数
        n = board[0].length;

        visited  = new boolean[m][n];

        for (int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                visited[i][j] = false;
            }
        }

        char[] words = word.toCharArray();
        /**
         * 可以从矩阵中任意的位置开始寻找单词的位置
         * 参见 Offer13 机器人的运动范围，初始位置只能是（0，0）
         */
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(searchdfs(board, words, 0,i, j)) return true;
            }
        }
        return false;
    }

    /**
     *在board中确定,board[startx][starty]范围是否有字符串匹配words[index]，然后向上下左右四个方向遍历，字符串为words[index,words.length]
     * @return
     */
    boolean searchdfs(char[][] board, char[] words, int index, int startx, int starty) {
        //退出条件 -- words中只有一个字母且这个字母[startx][starty]与board中的匹配
        if(index == words.length -1){
            if(board[startx][starty] == words[index]){
                return true;
            }else {
                return false;
            }
        }
        if(board[startx][starty]== words[index]){
            visited[startx][starty] = true;
            //向四个方向遍历
            for (int i = 0; i < 4; i++) {
                int newStartx = startx + direction[i][0];
                int newStarty = starty + direction[i][1];
//                System.out.println(index +"--"+newStartx+","+newStarty);
                //不越界，并且没有访问过
                if(inArea(newStartx, newStarty) && visited[newStartx][newStarty] == false){
                     if(searchdfs(board, words, index+1, newStartx, newStarty)){
                         return true;
                     }
                }
            }
            visited[startx][starty] = false;
        }
        return false;
    }

    /**
     * 确保坐标在矩形区域里
     * @param x
     * @param y
     * @return
     */
    public boolean inArea(int x, int y){
        if(x>=0 && x < m && y>=0 && y < n){
            return true;
        }
        return false;
    }
}
